package com.mlh.dp.old;

/*
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
举例：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

*/
//这题目和RobotWalk2类似
public class MinimumPathSum {
    // 初始位置0,0  目标位置m,n
    // int sitem,int siten 表示走到的位置
    // 暴力递归
    //在写递归的时候一定要明确 递归返回的东西是什么，才会去写递归体，要不然会迷迷糊糊的
    //这边返回的就是从sitem，siten位置走到重点的最小路径和
    public static int method1(int[][] grid, int sitem, int siten) {
        if (sitem == grid.length - 1 && siten == grid[0].length - 1) {
            return grid[sitem][siten];
        }
        if (sitem == grid.length - 1) {
            return method1(grid, sitem, siten + 1) + grid[sitem][siten];
        }
        if (siten == grid[0].length - 1) {
            return method1(grid, sitem + 1, siten) + grid[sitem][siten];
        }
        return Math.min(method1(grid, sitem + 1, siten), method1(grid, sitem, siten + 1)) + grid[sitem][siten];
    }

    // 记忆搜索
    public static int method2(int[][] grid, int sitem, int siten, int[][] pathSum) {
        if (pathSum[sitem][siten] != -1) {
            pathSum[sitem][siten]=grid[sitem][siten];
            return pathSum[sitem][siten];
        }

        if (sitem == grid.length - 1 && siten == grid[0].length - 1) {
            pathSum[sitem][siten] = grid[sitem][siten];
            return pathSum[sitem][siten];
        }
        if (sitem == grid.length - 1) {
            pathSum[sitem][siten] = method1(grid, sitem, siten + 1) + grid[sitem][siten];
            return pathSum[sitem][siten];
        }
        if (siten == grid[0].length - 1) {
            pathSum[sitem][siten] = method1(grid, sitem + 1, siten) + grid[sitem][siten];
            return pathSum[sitem][siten];
        }
        pathSum[sitem][siten] = Math.min(method1(grid, sitem + 1, siten) + grid[sitem + 1][siten], method1(grid, sitem, siten + 1) + grid[sitem][siten + 1]);
        return pathSum[sitem][siten];
    }

    //严格表依赖
    public static int method2(int[][] grid) {
        int resRow=grid.length;
        int resCol=grid[0].length;
        int[][]pathSum=new int[resRow][resCol];
        for(int i=0;i<pathSum.length;i++){
            for(int j=0;j<pathSum[0].length;j++){
                pathSum[i][j]=-1;
            }
        }
        pathSum[resRow-1][resCol-1]=grid[resRow-1][resCol-1];
        for(int i=resRow-2;i>=0;i--){
            pathSum[i][resCol-1]=pathSum[i+1][resCol-1]+grid[i][resCol-1];
        }
        for(int i=resCol-2;i>=0;i--){
            pathSum[resCol-1][i]=pathSum[resCol-1][i+1]+grid[resCol-1][i];
        }
        for(int i=resRow-2;i>=0;i--){
            for(int j=resCol-2;j>=0;j--){
                pathSum[i][j]=Math.min(pathSum[i+1][j],pathSum[i][j+1])+grid[i][j];
            }
        }
        return pathSum[0][0];
    }

}
